/**********************************************************

@description:
*File Name:graph.c
*Author: ydx
*mail: yudongxiang93@163.com
*Create Time: Wed 30 Apr 2025 10:53:12 PM CST
**********************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
//vexs not gothrough, the arc is MAX
//vexs gothrough with itself, the arc is 0
//
#define MAX 32767
typedef struct graph{
	char *vexs;
	int **arcs;
	int vex_num,arc_num;
}graph;
typedef struct edge{
	int start,end;
	int weight;
}edge;

edge* init_edge(graph* g){
	int index=0;
	edge* edge=(struct edge*)malloc(g->arc_num*sizeof(edge));
	assert(edge);
	for(int i=0;i<g->vex_num;i++){
		for(int j=i+1;j<g->vex_num;j++){
			if(g->arcs[i][j] != MAX){
				edge[index].start=i;
				edge[index].end=j;
				edge[index].weight=g->arcs[i][j];
				index++;
			}
		}
	}
	return edge;
}
void swap(edge* edge,int i,int j){
	struct edge tmp;
	tmp=edge[i];
	edge[i]=edge[j];
	edge[j]=tmp;
}
void sort_edge(edge* edge,int len){
	for(int i=0;i<len;i++){
		for(int j=0;j<len-i-1;j++){
			if(edge[j].weight>edge[j+1].weight){
				swap(edge,j,j+1);
			}
		}
	}
}
void kruskal(graph* g){
	int* connected=(int*)malloc(sizeof(int)*g->vex_num);
	for(int i=0;i<g->vex_num;i++){
		connected[i]=i;
	}
	edge *edge=init_edge(g);
	sort_edge(edge,g->arc_num);
	for(int i=0;i<g->arc_num;i++){
		printf("%d:%d ",i,edge[i].weight);
	}
	printf("\n");
	for(int i=0;i<g->arc_num;i++){
		printf("connected:");
		for(int k=0;k<g->vex_num;k++){
			printf("%d:%d  ",k,connected[k]);
		}
		printf("\n");
		int start=connected[edge[i].start];
		int end=connected[edge[i].end];
		if(start!=end){
			printf("v%c -- > v%c,weight=%d\n",g->vexs[edge[i].start],g->vexs[edge[i].end],edge[i].weight);
			for(int j=0;j<g->vex_num;j++){
#if 1
				if(connected[j]==end){
					connected[j]=start;
				}
#endif
			}
		}

	}
}

graph * init_graph(int vex_num){
	graph *g=(graph*)malloc(sizeof(graph));
	g->vexs=(char*)malloc(sizeof(char)*vex_num);
	g->arcs=(int**)malloc(sizeof(int*)*vex_num);
	for(int i=0;i<vex_num;i++){
		g->arcs[i]=(int*)malloc(sizeof(int)*vex_num);
	}
	g->vex_num=vex_num;
	g->arc_num=0;
	return g;
}
void createGraph(graph *g,char *vexs,int* arcs){
	for(int i=0;i<g->vex_num;i++){
		g->vexs[i]=vexs[i];
		for(int j=0;j<g->vex_num;j++){
			g->arcs[i][j]=*(arcs+i*g->vex_num+j);
			if(g->arcs[i][j] != 0 && g->arcs[i][j] != MAX){
				g->arc_num++;
			}
		}
	}
	g->arc_num/=2;
}
void dfs(graph *g,int* visited,int index){
	printf("%c\t",g->vexs[index]);
	visited[index]=1;
	for(int i=0;i<g->vex_num;i++){
		if(g->arcs[index][i]>0 && g->arcs[index][i] != MAX && !visited[i]){
			dfs(g,visited,i);
		}
	}
}
int main(){
	graph* g=init_graph(6);
	int arcs[36]={
		0,6,1,5,MAX,MAX,
		6,0,5,MAX,3,MAX,
		1,5,0,5,6,4,
		5,MAX,5,0,MAX,2,
		MAX,3,6,MAX,0,6,
		MAX,MAX,4,2,6,0,
	};
	createGraph(g,"123456",arcs);

	printf("dfs:");
	int *visited=(int*)malloc(sizeof(int)*g->vex_num);
	memset(visited,0,g->vex_num*sizeof(int));
	dfs(g,visited,0);
	printf("\n");
	kruskal(g);
	printf("\n");
	
}
